题解 CF1132E 【Knapsack】

发表于 | 更新于

$Description$

你有一个容量为$W$的背包，和$8$种物品，重量分别为$1\sim 8$的整数，分别有$cnt_1,cnt_2\cdots cnt_8$ 个。
求背包中最多能装上多大的重量。

$Solution$

由于$W$很大，我们首先可以选出一些肯定会放在最终背包里面的物品，我们假设把背包分成很多个容量为$840$的背包，我们可以知道的是，每种物品都可以单独装满这个背包，因为$840$是$1\sim 8$的最小公倍数，之后我们只要把所有能凑成的$840$的物品丢进最终的答案，最后每种物品剩余的个数肯定是$<840$的，最后这些物品的总重量是小于$840\times8$的，我们只需要用一个容量为$840\times8$的背包对剩下的这些物品进行背包就可以了。

若要对第$i$种物品选$c_i$个，那么把$c_i$分解成$\frac{L}{i}\times p_i+q_i(0\leqslant q_i <\frac{L}{i})$

具体实现时把最后剩下的物品当作容量，把$p_i$当成价值

最后统计取$max$

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define int long long
#define re register
#define inf 0x3f3f3f3f
#define N 600600
using namespace std;
const int L=840,n=8;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int c[N],f[10][N],ans;
signed main(){
	int W=read(),res=0;
	for (int i=1;i<=n;++i){
		c[i]=read();
		res+=c[i]*i;
	}
	if (res<=W){printf("%lld\n",res);return 0;}
	memset(f,-1,sizeof(f));
	f[0][0]=0;
	for (int i=1;i<=n;++i){
		int mx=min(c[i],L/i);
		for (int j=0;j<=L*n;++j)
			if (f[i-1][j]!=-1)
				for (int k=0;k<=mx;++k)
					f[i][j+k*i]=max(f[i][j+k*i],f[i-1][j]+(c[i]-k)/(L/i));
	}
	int ans=0;
	for (int i=0;i<=min(W,L*n);++i)
		if (f[n][i]!=-1)
			ans=max(ans,i+L*min(f[n][i],(W-i)/L));
	printf("%lld\n",ans);
    return 0;
}